package middle;

public class Solution_328 {

    public static void main(String[] args) {
        Solution_328 model = new Solution_328();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);
        node.next.next.next.next.next.next = new ListNode(7);
        node.next.next.next.next.next.next.next = new ListNode(8);
        model.oddEvenList(node);
        System.out.println();
    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next ==null) {
            return head;
        }
        ListNode one = head, twoHead = null, two = null;
        while (one.next != null) {
            ListNode node = one.next;
            if (twoHead == null) {
                two = node;
                twoHead = node;
            } else {
                two.next = node;
                two = node;
            }
            one.next = one.next.next;
            if (one.next != null) {
                one = one.next;
            }
            two.next = null;
        }
        one.next = twoHead;
        return head;
    }

    static class ListNode {
      int val;
      ListNode next;     ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
